package 力扣日常刷题.木22一月.第08天0116;

import java.util.Arrays;

/**
 * @author 帅小伙
 * @date 2022/1/16
 * @description
 */
public class Demo07动态规划中等模板找回文串个数 {




    public int countSubstrings(String s) {
        int n = s.length();
        int ans = n;
        if(n<=1)return n;
        boolean[][] dp = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i],true);
        }
        for (int i = n-1; i >= 0; i--) {
            for (int j = i+1; j < n; j++) {
                dp[i][j] = (s.charAt(i) == s.charAt(j))&&dp[i+1][j-1];
                if(dp[i][j]) ans++;
            }
        }
        return ans;
    }

}
